#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INF 0xfffffff
#define MM 10004
#define NN 1004
int edNum, N;
struct node{
       int e, v;
}edge[MM];

int next[MM];
int dis[NN];
int root[NN];
int que[NN];
int mark[NN];
int stack[NN];

void add(int a, int b, int c){
     int tmp;
     edge[edNum].e = b;
     edge[edNum].v = c;
     next[edNum] = root[a];
     root[a] = edNum++;
}

void Spfa()
{
     int i, quNum, tmp, nxt, cur;
     for (i = 1; i <= N; i++){
         dis[i] = INF;
     }
     dis[1] = 0;
     quNum = 0;
     for (i = 1; i <= N; i++){
         if (root[i] != -1){
            que[quNum++] = i;
            mark[i] = 1;
         }
     }

     for (i = 0; i != quNum; i = (i + 1) % (N + 1)){
         cur = que[i];
         tmp = root[cur];
         while (tmp != -1){
               nxt = edge[tmp].e;
               if (dis[nxt] > dis[cur] + edge[tmp].v){
                  dis[nxt] = dis[cur] + edge[tmp].v;
                  if (!mark[nxt]){
                     mark[nxt] = 1;
                     que[quNum] = nxt;
                     quNum = (quNum + 1) % (N + 1);
                  }
               }
               tmp = next[tmp];
         }
         mark[cur] = 0;
     }
}

void Spfa1()
{
     int i, top, tmp, nxt, cur;
     for (i = 1; i <= N; i++){
         dis[i] = INF;
     }
     dis[1] = 0;
     top = 0;

     for (i = 1; i <= N; i++){
         if (root[i] != -1){
            stack[++top] = i;
            mark[i] = 1;
         }
     }

     while (top){
         cur = stack[top--];
         tmp = root[cur];
         mark[cur] = 0;
         while (tmp != -1){
               nxt = edge[tmp].e;
               if (dis[nxt] > dis[cur] + edge[tmp].v){
                  dis[nxt] = dis[cur] + edge[tmp].v;
                  if (!mark[nxt]){
                     mark[nxt] = 1;
                     stack[++top] = nxt;
                  }
               }
               tmp = next[tmp];
         }

     }
}

int main()
{
    int M, a, b, c, i,t;
    scanf("%d",&t);
    while(t--)
    {
    scanf("%d%d", &N, &M);
    edNum = 0;
    for (i = 0; i <= N; i++){
        root[i] = -1;
        mark[i] = 0;
    }
    while (M--){
          scanf("%d%d%d", &a, &b, &c);
          add(a, b, c);
    }
    Spfa1();
    printf("%d\n", dis[N]);
    }
    return 0;
}
